/* 
 * File:   seq_gen.c
 * Author: TuanND
 *
 * Created on September 6, 2013, 3:24 PM
 * 
 * This is nothing but the detail implementation of Hamming Sequence Generator Lib
 * which was described in seq_gen.h (please look at seq_gen.h for abstract and logic description 
 * of my program. 
 * 
 * First, I implemented list operations (list_new, list_add, ...). They are supporting functions so 
 * please look at each function documentation for more detail. 
 * 
 * Second, the core function is sequence_generator with two helper are merge_list and check_list functions.
 *
 * Here's the key steps in my algorithm implementation.
 * 1.Create 4 lists of type struct hList*
 *      -Final List: the list which includes all sorted Hamming number after step N. It's redundant so we have to extract it.
 *              +Step 1: Final list includes {2,3,5}
 *              +     2:                     {2,3,5,4,6,9,10,15,25}
 *              +     N:                     {2^i*3^j*5^k | i+j+k <= N}
 *      -Temp List: the temporary sorted list to transfer to Final List
 *              +Initialization (Step 1): {2,3,5}
 *              +Step 2: {4,6,9,10,15,25}
 *              +Step N: {2^i*3^j*5^k | i+j+k = N}
 *              Generally, Temp List = Merge (List 2_Term, List 3_Term, List 5_Term)
 *      -List 2_Term (Step N) = Temp List (Step N-1) * 2
 *      -List 3_Term (Step N)= Temp List (Step N-1) * 3
 *      -List 5_Term (Step N)= Temp List (Step N-1) * 5
 * 2.We repeatly check the final list after each step, 
 *      -if we have enough Hamming number in there -> stop, extract and print
 *      -otherwise, compute the new Terms List, then merge them to have the new Temp List 
 *       and finally, merge with current Final List to have new Final List and check again.
 * 3.The steps here (merge two sorted lists, or multiple a list with a scalar) are simple 
 * EXCEPT how can we check how many in final list are first Hamming Number? 
 * For example: Final list Step 1: {2,3,5} -> 2 numbers {2,3}
 *                              2: {2,3,4,5,6,9,10,15,25} -> 5 numbers {2,3,4,5,6}
 * 
 * SOLUTION:    Based on looking at first steps, we make a hypothesis:
 *              At Step N: Every number in Final List which < 2^(N+1) is safe to extract.
 *              Look at Step 1, 2: {2,3}<2^2 and {2,3,4,5,6}<2^3.
 * PROOF:       Recall Final List (Step N) = {2^i*3^j*5^k | i+j+k <= N};
 *              Clearly, 2^(N+1) is the least Hamming number which is NOT belong to Final List (Step N).
 *              Moreover,we have 3*2^(N-1) < 2^(N+1) < 5*2^(N-1) -->  2^(N+1) is the least Hamming number
 *              which both is NOT belong to Final List (Step N) and is in between 2 continuous Hamming number in Final List (Step N).
 * ==> Hypothesis is right.
 * 
 */

#include "seq_gen.h"

/*******************************************************************************
 * MAIN APPLICATION (RUN/TEST/DEBUG ENTRY)
 ******************************************************************************/
int main(int argc, char** argv) {

    int N; //prefix-length of the desired sequence
    printf("Enter the prefix-length N: ");    
    scanf("%d", &N);
    printf("\n-----------------------------------------------------------");
    struct hList* pHammingSeq = sequence_generator(N);
    printf("\nHamming Sequence:\n");
    list_print(pHammingSeq);
    printf("\n-----------------------------------------------------------\n");
    getchar();
}

/*******************************************************************************
 *LIST OPERATIONS IMPLEMENTATION
 ******************************************************************************/

/**
 * Add a new element to current list
 * @param pList: current list
 * @param newNum: a new number
 * @return a list which new number was included
 */
struct hList* list_add(struct hList* pList, const long newNum) {
    if (pList == NULL) {
        printf("List was not initialized. Should initialize list before adding elements");
    } else {//List was initialized already
        //Create a new element
        struct hNum* pNum = malloc(sizeof (*pNum));
        pNum->num = newNum;
        pNum->next = NULL;
        //Append it to the end of list
        if (pList->end == NULL) {//if no elements in list
            //point both start and end pointers to new element
            pList->end = pNum;
            pList->start = pNum;
        } else {//if list has some elements
            //append new element to the end
            pList->end->next = pNum;
            pList->end = pNum;
        }
    }
    return pList;
}

/**
 * Create a new list (allocate memory for 2 pointers)
 * @return a new list
 */
struct hList* list_new(void) {
    struct hList* pList = malloc(sizeof (*pList));
    pList->start = pList->end = NULL;
    return pList;
}

/**
 * Print a list to screen (standard output)
 * @param pList: a list to print
 */
void list_print(const struct hList *pList) {
    if (pList != NULL) {//If list was initialized
        if (pList->end != NULL) {//If list is not empty
            struct hNum* pNum = pList->start;
            printf("{");
            while (pNum != NULL) {
                if (pNum->next != NULL) {
                    printf("%d,", pNum->num);
                } else {
                    printf("%d", pNum->num);
                }
                pNum = pNum->next;
            }
            printf("}");
        } else {//If list is empty
            printf("{}");
        }

    } else {//list was not initialized
        printf("Warning: List was not initialized!");
    }
}

/**
 * Extract a sub-list from a longer list
 * @param pList: longer list
 * @param length: length to extract
 * @return : sub-list
 */
struct hList* list_sub(struct hList* pList, int length) {
    struct hList* pSubList = NULL;
    if ((pList == NULL) || (pList->start == NULL)) {
        printf("Subtract a NULL/EMPTY list!!!");
        return NULL;
    } else {
        struct hNum* pNum = pList->start;
        int count = 0;
        while (pNum != NULL) {
            count = count + 1;
            pNum = pNum->next;
        }
        if (count < length) {
            printf("Sub-list is longer than mother list!!!");
            return NULL;
        } else {
            pNum = pList->start;
            pSubList = list_new();
            count = 0;
            while ((pNum != NULL)&&(count < length)) {
                list_add(pSubList, pNum->num);
                pNum = pNum->next;
                count = count + 1;
            }
        }
    }
    return pSubList;
}

/**
 * Multiple a list with a scale factor
 * @param pList: list should be scaled
 * @param scale: scale factor
 * @return : new list
 */
struct hList* list_scale(struct hList *pList, int scale) {
    struct hList* pScaledList = NULL;
    if (pList == NULL) {
        printf("Warning: List was not initialized!");
    } else {
        if (pList->end == NULL) {
            printf("List is empty");
        } else {
            pScaledList = list_new();
            struct hNum* pCurNum = pList->start;
            while (pCurNum != NULL) {
                long scaledNum = pCurNum->num * scale;
                list_add(pScaledList, scaledNum);
                pCurNum = pCurNum->next;
            }
        }
    }
    return pScaledList;
}

/*******************************************************************************
 * ALGORITHM FUNCTIONS IMPLEMENTATION
 *******************************************************************************/

struct hList* sequence_generator(int N) {
    /*
     * VARIABLE DECLERATION
     */
    struct hList *pLFinal, //List of all terms of the desired sequence
            *pLTemp, //(2,3,5) at the beginning, contains some, but not all, of the terms of the desired sequence that are transfered to pLFinal
            *pL2, //generated by multiplying the current contents of pLTemp by 2
            *pL3, //generated by multiplying the current contents of pLTemp by 3
            *pL5 = NULL; //generated by multiplying the current contents of pLTemp by 5
    /*
     * INITIALIZATION
     */
    pLFinal = list_new();
    pLTemp = list_new();
    pL2 = list_new();
    pL3 = list_new();
    pL5 = list_new();

    list_add(pLTemp, 2);
    list_add(pLTemp, 3);
    list_add(pLTemp, 5);

    /*
     * START ALGORITHM
     */
    int step = 1;
    int hCount = 0; //current safety number of final list    
    struct hNum* pLast = NULL;

    //Step 1. Compute new Final List from current Temp List
    pLFinal = merge_list(pLFinal, pLTemp);
    pLast = check_list(pLFinal, step, &hCount);

    while (hCount < N) {//while we don't have enough hamming number        
        step = step + 1;
        //printf("\nStep %d \n", step);

        //1. Compute 3 new Term Lists
        pL2 = list_scale(pLTemp, 2);
        pL3 = list_scale(pLTemp, 3);
        pL5 = list_scale(pLTemp, 5);

        //2. Merge them all to replace the old Temp List
        struct hList* tempList = merge_list(pL2, pL3);
        pLTemp = merge_list(tempList, pL5);

        //3. Merge new Temp List with Current Final List
        pLFinal = merge_list(pLFinal, pLTemp);

        //4. Compute new hCount
        pLast = check_list(pLFinal, step, &hCount);
    }
    //Finally, we have a longer list than prefix-length which user required
    //extract the n-length correct terms list
    struct hList* pCorrect = list_sub(pLFinal, N);
    return pCorrect;
}

/**
 * Merge 2 sorted lists into 1 sorted list
 * @param pListA: one of two lists
 * @param pListB: one of two lists
 * @return : result list
 */
struct hList* merge_list(struct hList *pListA, struct hList *pListB) {
    struct hList* pResultList = NULL;
    if ((pListA == NULL) || (pListA->start == NULL)) {
        pResultList = pListB;
    } else {
        if ((pListB == NULL) || (pListB->start == NULL)) {
            pResultList = pListA;
        } else {//If listA and listB is not empty
            struct hNum* pCurA = pListA->start;
            struct hNum* pCurB = pListB->start;
            pResultList = list_new();

            while ((pCurA != NULL) || (pCurB != NULL)) {
                //If A.end reached, append the rest of B to result List, and vice versa.
                if (pCurA == NULL) {
                    while (pCurB != NULL) {
                        list_add(pResultList, pCurB->num);
                        pCurB = pCurB->next;
                    }
                } else if (pCurB == NULL) {
                    while (pCurA != NULL) {
                        list_add(pResultList, pCurA->num);
                        pCurB = pCurA->next;
                    }
                } else {
                    if (pCurA->num < pCurB->num) {//if A[i]<B[j] merge A[i], i = i+1
                        list_add(pResultList, pCurA->num);
                        pCurA = pCurA->next;
                    } else if (pCurA->num > pCurB->num) {//if A[i] > B[j] merge B[j], j = j+1
                        list_add(pResultList, pCurB->num);
                        pCurB = pCurB->next;
                    } else {//if A[i] == B[j] merge B[j], i++ and j++
                        list_add(pResultList, pCurB->num);
                        pCurA = pCurA->next;
                        pCurB = pCurB->next;
                    }
                }
            }
        }
    }
    return pResultList;
}

/**
 * Check the final list to know how much of it is safe
 * @param pList: list to check
 * @param step: current step count
 * @param hCount: number of safe numbers in list
 * @return : the last safe number
 */
struct hNum* check_list(struct hList *pList, int step, int* hCount) {
    int count = 0;
    long thresh = (long) pow((double) 2, step + 1);

    struct hNum* pLast = NULL;
    struct hNum* pNum = NULL;
    if ((pList != NULL) || (pList->start != NULL)) {
        pNum = pList->start; //get the first element
        while ((pNum != NULL)&&(pNum->num < thresh)) {//while it < thresh
            count = count + 1;
            if (pNum->next == NULL) {//reach the end
                pLast = pNum;
            } else if (pNum->next->num > thresh) {//over the threshold
                pLast = pNum;
            }
            pNum = pNum->next;
        }
    } else {
        printf("Checking on a NULL/EMPTY list!");
        return NULL;
    }
    *hCount = count;
    return pNum;
}

